class Ex2
  
  def calculate(n)
    (n-1).downto(2) do |i|
      if (prime(i) || power_prime(i)) then
        puts(i)
      end
    end
  end
  
  def prime(x)
    for i in 2..(Math.sqrt(x)).floor
      if (x % i == 0)
        return false
      end
    end
    return true
  end
  
  
  def power_prime(x)
    for i in 2..(Math.sqrt(x)).floor
      j = 1
      if prime(i)
        while i ** j <= x
          if i ** j == x
            return true
          end
          j = j + 1
        end
      end
    end
    return false
  end
  
end

  puts "Nhap n nguyen:"
  n = gets.chomp.to_i
  ex2 = Ex2.new()
  ex2.calculate(n)
